# -*- coding: utf-8 -*-
"""
Created on Sun Sep 20 16:52:36 2020

@author: Administrator
"""

'''

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true
Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false
'''

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
            '''
            
            20200920--李运辰
            '''
            if len(matrix)==0:
                return False
            if len(matrix[0])==0:
                return False
            m=len(matrix)
            res = matrix[0]
            f = True
            for i in range(m):
                if matrix[i][0]==target:
                    res = matrix[i]
                    f =False
                    break;
                if matrix[i][0]>target:
                    if i>=1:
                        res = matrix[i-1]
                        f =False
                    else:
                        res = matrix[i]
                        f =False
                    break;
              
            if f:
                res=matrix[i]
           
            for i in res:
                if i==target:
                    return True
            return False